import ListNode from "./ListNode"

export default class LinkedList<T> {

    private head: ListNode<T> | null
    private tail: ListNode<T> | null
    private len: number

    constructor() {
        this.head = this.tail = null
        this.len = 0
    }

    /**
     * 向链表尾部添加节点
     * @param value 要添加的节点的值
     */
    protected add(value: T): void {
        const newNode = new ListNode<T>(value)
        if (this.tail !== null) {
            this.tail.next = newNode
            this.tail = newNode
        } else {
            this.head = this.tail = newNode
        }
        this.len++
    }

    /**
     * 向链表头部插入节点
     * @param value 要插入的节点的值
     */
    protected insert(value: T): void {
        const newNode = new ListNode<T>(value)
        newNode.next = this.head
        this.head = newNode
        this.len++
    }

    /**
     * 返回是否是空链表
     * @returns 头节点是否为NULL
     */
    isEmpty(): boolean {
        return this.head === null
    }

    protected getLast(): T | undefined {
        return this.tail?.value
    }

    protected getFirst(): T | undefined {
        return this.head?.value
    }

    protected removeLast(): T | undefined {
        let beforeLast: ListNode<T> | null = this.head
        if (this.len < 2) {
            this.head = this.tail = null
            return beforeLast?.value
        } else {
            const last = this.tail
            while (beforeLast) {
                if (beforeLast.next === last) {
                    beforeLast.next = null
                    this.tail = beforeLast
                    break
                }
                beforeLast = beforeLast.next
            }
            return last?.value
        }
    }

    protected removeFirst(): T | undefined {
        const node = this.head
        if (node !== null) {
            this.head = node.next
        }
        this.len--
        return node?.value
    }

    protected indexOf(dest: ListNode<T>): number {
        let node: ListNode<T> | null = this.head
        let index: number = -1
        while (node !== null) {
            index++;
            if (node === dest) {
                return index
            }
            node = node.next
        }
        return -1
    }

    protected length(): number {
        return this.len
    }
}